def lcs_length(X,Y,i,j,c):
    if i==-1 or j==-1:
        c[i+1,j+1]=0
        return
    if X[i]==Y[j]:
        if (i,j) not in c:
            lcs_length(X,Y,i-1,j-1,c)
        c[i+1,j+1]=c[i,j]+1
    else:
        if (i,j+1) not in c:
            lcs_length(X,Y,i-1,j,c)
        if (i+1,j) not in c:
            lcs_length(X,Y,i,j-1,c)
        if c[i,j+1]>=c[i+1,j]:
            c[i+1,j+1]=c[i,j+1]
        else:
            c[i+1,j+1]=c[i+1,j]
def do_lcs_length(X,Y):
    c={}
    m=len(X)
    n=len(Y)
    lcs_length(X,Y,m-1,n-1,c)
    return c
def do_print_lcs(c,X,Y):
    m=len(X)
    n=len(Y)
    print_lcs_without_b(c,X,Y,m-1,n-1)
def print_lcs_without_b(c,X,Y,i,j):
    if i==-1 or j==-1:
        return
    if X[i]==Y[j]:
        print_lcs_without_b(c,X,Y,i-1,j-1)
        print X[i],
    elif c[i,j+1]>=c[i+1,j]:
        print_lcs_without_b(c,X,Y,i-1,j)
    else:
        print_lcs_without_b(c,X,Y,i,j-1)

if __name__=='__main__':
    X='ABCBDAB'
    Y='BDCABA'
    print 'X:',X
    print 'Y:',Y
    c=do_lcs_length(X,Y)
    print 'LCS:',
    do_print_lcs(c,X,Y)
